The Twofish Encryption Algorithm: A 128-Bit Block Cipher The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson
Wiley Computer Publishing, John Wiley & Sons, Inc.
ISBN: 0471353817   Pub Date: 03/01/99
  

Previous Table of Contents Next


Our solution is as follows: If we flip the same bits in g(C) as in g(D), then the sum g(C) + g(D) will be unchanged, and as a result, the effect of the input difference in c1, d1 will also be unchanged. Let x3, y3 be the bytes that actually go into the S-box s3 in the two g functions. We control c3, d3, but their values axe XORed with some unknown bytes before being used as x3, y3. Thus,

x3 = c3z3

y3 = d3z4

We need to be able to choose c3, d3 so that x3 = y3. If we ever did that, then we could generate 255 additional cases where y3 = z3, simply by XORing 1,...,255 into both c3 and d3. Now, if we knew z3z4, we could choose any c3 value we liked, and then set d3 = c3z3z4, giving us x3 = y3. We thus try all 256 possible values for z3z4. One of those values is right; we can use it to take a single right pair, and produce 255 more just like it. This is done by keeping A and B constant, and by choosing

C = (c0, c1, c2, c3i)

D = (d0, d1, d2, d3iz3z4)

C* = (c0, c*1, c2, c3i)

D* = (d0, d*1, d2, d3iz3z4)

where c1, d1, and c*1, d*1 are the bytes changed in the original right pair. For each potential right pair, we thus generate 256 pairs of text according to the above formula for each guess about z3z4. This means that each potential right pair generates 256 batches of 256 pairs of plaintexts (and corresponding pairs of ciphertexts), or a total of 216 plaintext pairs. Thus, n0 = 256.

Deriving a Right Pair from a Partial Right Pair. Suppose we have a pair of texts, (C, D), (C*, D*), such that g(C) ⊕ g(C*) = g(D) ⊕ g(D*), with that XOR difference having Hamming weight of 8. In most (255/256) cases, this won’t be a right pair, because g(C) + g(D) ≠ g(C*) + g(D*). To turn this into a right pair, some of the bits in g(C) which axe covered by the XOR difference need to be flipped. We thus choose the available bytes, c0 and c2, and vary both bytes randomly in different texts. After about 256 different random c0, c2 choices, we expect to derive a real right pair from the partial right pair. Naturally, most of the pairs we generate will not be right pairs, and we won’t be able to distinguish them from wrong pairs until we mount the attack.

We thus determine that n1 = 256.

Finding a Single Partial Right Pair. A partial right pair can be found by getting the same XOR difference out from the S-box determined by c1 and also by d1. We don’t know the S-box these are going through, but simulations show that if we try i, i ⊕ δ as a pair of inputs into a random 8-bit-wide bijective S-box, s, we have a probability of 1/2 of getting any desired output XOR difference. If there axe three XOR differences that lead, after the MDS matrix is applied, to 8-bit XOR differences, then the probability is thus 7/8 that this approach will work to find a partial right pair.

We have the same complications we did above: we control c1, d1, but we need to control x1 = c1z1,y1 = d1z2, the inputs to the S-boxes in the two g functions. Similarly to the way we dealt with this above, we end up guessing z1z2. The result is that we generate 216 plaintext pairs, of which at least one is almost certainly a partial right pair. Thus, n2 = 216.

Testing a Batch of Plaintext Pairs. We generate n0n1n2 = 2828216 = 232 batches of plaintext pairs. During our attack, we must guess as much of the key material as is required, and for each guess, we must test each batch to see if it is made up of only right pairs. The probability of a randomly-selected key giving us a “false positive”—that is, a batch that appears to be right but is not—is 2-256. This probability is low enough that we never expect a single false positive.

We now consider the difficulty of testing one such batch of plaintext pairs. The question is how many trial partial decryptions we must do for each batch, on average, before determining that the batch is not made up of only right pairs. For a guessed partial key, each batch will yield a sequence of 256 bits; in the batch of right pairs, they will all be the expected bit. However, for each batch, we can stop searching as soon as we find a single bit that is different than the others. The expected number of trial partial decryptions required per batch is thus

2 · 1/2 + 3 · 1/4 + 4 · 1/8 + ··· + (n + 1) · 1/2n ≈ 3

Each partial decryption is less work than a full encryption. We take n3 = 1 for our estimates, which corresponds to each partial decryption being one-third as much work as a full encryption.

9.2.4 Mounting the Attack

To mount the attack, we must determine what key material must be guessed to check our batches. Consider a 5-round Twofish variant without whitening and without the 1-bit rotations. In this case, we need only guess S. Recall that in a right pair, we know the difference in only one bit—the low-order bit of D in this case—at the input to the fifth round. After guessing S, we can compute the value of the g function that uses A as its input in the fifth round. The low-order bit of this is XORed with the low-order bit of the corresponding subkey, and then XORed into the bit whose difference we know. Knowledge of the low-order bit of that g output thus gives us the desired bit difference.

To extend this another round, we must also guess the subkey in the sixth round that affects the value XORed into A. Because we only have to get the low bit of D, we need not compute the B value input into the fifth round’s F function at all. This requires 232 additional work.

To extend this one more round, we must guess the whole set of round subkeys in the next round. This requires 264 additional work.

Five-round Twofish consists of ten g computations and a little extra work. To be conservative, we can consider each g computation to be 1/8 of a trial encryption.

Key Length Rounds Work(equiv. trial encs.)
128 5 230 · 264 = 294
128 6 230 · 296 = 2126
192 5 230 · 296 = 2126
192 6 230 · 2128 = 2158
256 5 230 · 2128 = 2158
256 6 230 · 2160 = 2190
256 7 230 · 2224 = 2254

Table 9.3. Differential Attack Results against a Variant with No Whitening and No Rotations

Key Length Rounds Work(equiv. trial encs.)
128 5 230 · 274 = 2104  
128 6 230 · 2138 = 2166 (No longer useful.)
192 5 230 · 2106 = 2136  
192 6 230 · 2170 = 2200 (No longer useful.)
256 5 230 · 2138 = 2168  
256 6 230 · 2202 = 2232  
256 7 230 · 2266 = 2296 (No longer useful.9)

Table 9.4. Differential Attack Results against a Variant with No Whitening

Thus, for five- to seven-round Twofish with no whitening and no 1-bit rotates, we have the results summarized in Table 9.3.2 (Note that all of these results are for 241 chosen plaintexts.)


2We are indebted to Eli Biham for the suggestion of guessing the whole last round’s subkeys for the 256-bit key.

When we add back in the 1-bit rotates, the attacks grow substantially harder. (Interestingly, though we put the 1-bit rotates in because of concerns about the byte structure, so far, the 1-bit rotates have complicated several attacks based on exploiting properties of the low bit of one of the PHT words.) We must now learn both g function outputs in the fifth round, as well as guessing the high-order 10 or so bits of round subkey used to alter the value XORed into D in the fifth round. We list the resulting attack complexities in Table 9.4.

The whitening also adds a little difficulty. When combined with the 1-bit rotates, we get the results summarized in Table 9.5. We note that there are straightforward differential attacks on four rounds that work despite the 1-bit rotations and whitening, but they involve using only the (0, X) → (?, (?, 1)) differential.

Key Length Rounds Work(equiv. trial encs.)
128 5 230 · 2128 = 2158 (No longer useful.)
192 5 230 · 2170 = 2200 (No longer useful.)
256 5 230 · 2202 = 2232  

Table 9.5.3 Differential Attack Results against Reduced Rounds

Key Length Rounds Work(equiv. trial encs.)
all 6 230 · 232 = 262
all 7 230 · 296 = 2126
192 & 256 8 230 · 2160 = 2190
256 9 230 · 2224 = 2254

Table 9.6. Differential Attack Results on a Variant with Known S and No Rotations

Finally, we can consider the difficulty of this attack on a Twofish variant with a fixed, known S value and no 1-bit rotates. In this case, we have the difficulties results listed in Table 9.6.

Again, this demonstrates how the additional key material in the key-dependent S-boxes adds to the practical difficulty of an attack. Additionally, with fixed S-boxes, it may be possible for the attacker to get a substantial improvement, perhaps by as much as a factor of 256, on the number of plain-text batches he must request. This would reduce the plaintext requirement and the work factors on all these attacks by the same factor.


Previous Table of Contents Next